class Solution {
    /*
        思路1：双向队列，主要难点为java中链表的插入、值传递
        空间复杂度：O(N)
    */
    public void reorderList(ListNode head) {
        Deque<ListNode> q = new LinkedList<>();
        ListNode tmp = head;
        while(tmp!=null){
            q.offerLast(tmp);
            tmp = tmp.next;
        }
        while(!q.isEmpty()){
            ListNode p1 = q.pollFirst();
            ListNode p2 = q.pollLast();
            if(p1!=null){
                head.next = p1;
                head = p1;
            }
            if(p2!=null){
                head.next = p2;
                head = p2;
            }
            head.next = null;
        }
    }
}
class Solution {
    /*
        解法2：使用列表，难点为java中链表的插入
    */
    public void reorderList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode tmp = head;
        while(tmp != null){
            list.add(tmp);
            tmp = tmp.next;
        }
        int i = 0,j = list.size()-1;
        while(i < j){
            ListNode p1 = list.get(i++);
            head.next = p1;
            head = p1;

            ListNode p2 = list.get(j--);
            head.next = p2;
            head = p2;
        }
        if(i == j){
            head.next = list.get(i);
            head = list.get(i);
        }
        head.next = null;
    }
}
class Solution {
    /*
            解法3：使用列表，但是优化了插入的逻辑。。。
     */
    public void reorderList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode tmp = head;
        while(tmp != null){
            list.add(tmp);
            tmp = tmp.next;
        }
        int i = 0,j = list.size()-1;
        while(i < j){
            list.get(i).next = list.get(j);
            i++;
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}
class Solution {
    /*
        解法4：找中点-》链表逆置-》合并链表
    */
    public void reorderList(ListNode head) {        
        // 1.找中点
        ListNode midNode = getMidNode(head);
        
        // 2.逆置中点后的链表
        ListNode l2 = reverse(midNode.next);
        midNode.next = null;
        
        // 3.链表合并
        merge(head,l2);
        
        
    }
    // 找到链表中点
    public ListNode getMidNode(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode pre = head;
        while( head!=null && head.next!=null ){
            pre = pre.next;
            head = head.next.next;
        }
        return pre;
    }
    // 逆置链表
    public ListNode reverse(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode pre = null;
        while(head!=null){
            // System.out.print(head.val+"-");
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
    // 合并l1,l2
    public void merge(ListNode l1,ListNode l2){
        while(l1!=null && l2!=null){
            ListNode tmp1 = l1.next;
            ListNode tmp2 = l2.next;
            l1.next = l2;
            l1 = tmp1;
            l2.next = l1;
            l2 = tmp2;
        }
    }
}